package Aula7Maio_ArvRed_Black;

public class ArvoreRedBlack extends ArvorePesquisaBinaria
{
	int [] color = null;
	final int BLACK = 0;
	final int RED = 1;
	int [] right = null;
	int [] left = null;
	int [] p = null;
	
	public ArvoreRedBlack(int n)
	{
		super(n);
		color = new int [n];
		right = this.m.right;
		left = this.m.left;
		p = this.m.p;
	}
	
	public void left_rotate(int x)
	{
		int y = right[x];
		right[x] = left[y];
		if(left[y] != NIL);
		{
			p[left[y]] = x;
		}
		
		p[y] = p[x];
		if(p[x] == NIL)
			root = y;
		else if	(x == p[left[x]])
			p[left[x]] = y;
		else
			right[p[x]]= y;
		left[y] = x;
		p[x] = y;
			
	}
	
	public void right_rotate(int x)
	{
		int y = left[x];
		left[x] = right[y];
		if(right[y] != NIL);
		{
			p[right[y]] = x;
		}
		
		p[y] = p[x];
		if(p[x] == NIL)
			root = y;
		else if	(x == p[right[x]])
			p[right[x]] = y;
		else
			left[p[x]]= y;
		right[y] = x;
		p[x] = y;
		
	}
	
	public void insert(int key)
	{
		super.insert(key);
		color[z] = RED;
		System.out.print("z =");
		System.out.println(z);
		insert_fixup(z);
	}
	
	@Override public String toString()
	{
		String s = super.toString();
		StringBuilder res = new StringBuilder();
		res.append("\n");
		
		for(int k = color.length-1; k >=0; k--)
		{
			res.append(k);
			res.append("-> color =");
			res.append(color[k] == 0 ? "BLACK" : "RED");
			res.append("\n");
		}
		
		return s+ res;
		
	}
	
	public void insert_fixup(int z)
	{
		int y = 0;
		while (color[p[z]]== RED)
		{
			if(p[z] == left[p[p[z]]])
			{
				y = right[p[p[z]]];
				if(color[y] == RED)
				{
					color[p[z]]= BLACK;
					color[y] = BLACK;
					color[p[p[z]]] = RED;
					z = p[p[z]];
					
				}
				else
				{
					if(z == right[p[z]])
					{
						z = p[z];
						left_rotate(z);
					}
					color[p[z]] = BLACK;
					color[p[p[z]]] = RED;
					right_rotate(p[p[z]]);
					
				}
			}
			else
			{
				y = left[p[p[z]]];
				if(color[y]== RED)
				{
					color[p[z]] = BLACK;
					color[y] = BLACK;
					color[p[p[z]]] = RED;
					z = p[p[z]];
				}
				else
				{
					if(z == left[p[z]])
					{
						z = p[z];
						right_rotate(z);
					}
					color[p[z]] = BLACK;
					color[p[p[z]]] = BLACK;
					left_rotate(p[p[z]]);
				}
			}
		}		
		
	
	color[root] = BLACK;
	}
}
